package leetcode.l0531;

/**
 * @author Retain
 * @date 2021/5/31 20:42
 */
public class Easy_比特位计数_338 {
    public static void main(String[] args) {
        System.out.println(24 & 23);
    }
    public int[] countBits(int n) {
        int[] ints = new int[n+1];
        for (int i = 0; i <= n; i++) {
            ints[i] = Integer.bitCount(i);
        }
        return ints;
    }

    /**
     * i & (i - 1) 不管最右边有多少0，都不影响，只会把从右到左第一个1变成0，根据dp数组查找该数1的个数，最后再+1
     * @param num
     * @return
     */
    public int[] countBits2(int num) {
        int[] res = new int[num + 1];
        for(int i = 1;i<= num;i++){  //注意要从1开始，0不满足
            res[i] = res[i & (i - 1)] + 1;
        }
        return res;
    }
}
